class Node {
    constructor(key = 0, value = 0) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.dummy = new Node(); // 哨兵结点
        this.dummy.prev = this.dummy;
        this.dummy.next = this.dummy;
        this.cache = new Map(); // 缓存
    }

    getNode(key) {
        if (!this.cache.has(key)) { // 没有这个节点
            return null;
        }
        const node = this.cache.get(key);
        this.remove(node);
        this.moveToHead(node);
        return node;
    }

    get(key) {
        const node = this.getNode(key);
        return node ? node.value : -1;
    }

    put(key, value) {
        let node = this.getNode(key);
        if (node) { // 有这个节点
            node.value = value;
            return;
        } 
        node = new Node(key, value); // 新节点
        this.cache.set(key, node);
        this.moveToHead(node); // 放在头
        if (this.cache.size > this.capacity) {
            const backNode = this.dummy.prev;
            this.cache.delete(backNode.key);
            this.remove(backNode);
        }

    }

    // 移除一个节点
    remove(cur) {
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
    }

    // 在链表头添加一个节点
    moveToHead(cur) {
        cur.prev = this.dummy;
        cur.next = this.dummy.next;
        cur.prev.next = cur;
        cur.next.prev = cur;
    }

}